package formal.tree.bst;

/**
 * 二叉搜索树的最近公共祖先
 * @author DengYuan2
 * @create 2021-01-23 20:53
 */
public class E_235 {
    public static void main(String[] args) {
        Integer[] a ={6,2,8,0,4,7,9,null,null,3,5,null,null,null,null};
        TreeNode treeNode = TreeNode.generateTree(a);
        TreeNode res = lowestCommonAncestor2(treeNode, new TreeNode(9), new TreeNode(8));
        System.out.println(res);
    }

    /**
     * 我的写法-和大神一致
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (root==null){
//            return null;
//        }
        if (p.val<root.val&&q.val<root.val){
            return lowestCommonAncestor(root.left,p,q);
        }else if (p.val>root.val&&q.val>root.val){
            return lowestCommonAncestor(root.right,p,q);
        }else {
            return root;
        }
    }

    /**
     * 官方-迭代-思路一致
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
        TreeNode target = root;
        while (true){
            if (target.val<p.val&&target.val<q.val){
                target=target.right;
            }else if (target.val>p.val&&target.val>q.val){
                target=target.left;
            }else {
                return target;
            }
        }
    }
}
